//
// Created by 徐林鑫 on 2024/1/26.
//

#include <map>
#include <set>
#include <assert.h>
#include <iostream>
#include <stack>
#include <sstream>
#include <cstring>
#pragma  warning (disable: 4996)
using namespace std;
#define MaxVertices_size 10 //最大顶点数大小

//表示边的节点结构
struct EdgeNode{
    int curridx;//边对应的顶点下标值
    EdgeNode* next;//指向下一条边
};
//表示顶点的节点结构，其后是一个链表，链表中每个节点都代表着和该顶点相连的边
template<typename T>//T代表顶点类型
struct VertexNode{
    T data;//顶点中的数据
    EdgeNode* point;//指向第一个边节点的指针
};

//邻接表代表的图
template<typename T>
class GraphLink{
private:
    int m_numVertices;//当前顶点数量
    int m_numEdges;//边的数量
    VertexNode<T> m_VertexArray[MaxVertices_size];//顶点数组
    int GetVertexIdx(const T& tmpv){
        for(int i = 0;i < m_numVertices ; i++){
            if(m_VertexArray[i].data == tmpv){
                return i;
            }
        }
        return -1;//不存在该节点
    }
public:
    GraphLink(){   //构造函数
        m_numVertices = 0;
        m_numEdges =0;
        for (int i=0;i < MaxVertices_size;i++){
            m_VertexArray[i].point = nullptr;  //指针可以率先指向
        }
    }
    ~GraphLink(){  //析构函数
        for (int i=0;i < MaxVertices_size;i++){
            EdgeNode* ptmp = m_VertexArray[i].point;
            while (ptmp != nullptr){
                m_VertexArray[i].point = ptmp->next;
                delete ptmp;
                ptmp = m_VertexArray[i].point;
            }
            m_VertexArray[i].point = nullptr;
        }
    }
    //插入顶点
    bool InsertVertex(const T& tmpv){
        if (m_numVertices >= MaxVertices_size){
            cout<<"邻接表已满，无法插入顶点！"<<endl;
            return false;
        }
        if (GetVertexIdx(tmpv)!=-1){
            cout<<"邻接表已经有该顶点，请勿重复插入！"<<endl;
            return false;
        }
        m_VertexArray[m_numVertices].data = tmpv;
        m_VertexArray[m_numVertices].point = nullptr;
        m_numVertices++;
        return true;
    }
    //插入边
    bool InsertEdge(const T& tmpv1,const T& tmpv2){
        int idx1 = GetVertexIdx(tmpv1);
        int idx2 = GetVertexIdx(tmpv2);
        if (idx1 == -1 || idx2 ==-1){
            cout<<"存在非法顶点，无法插入边！"<<endl;
            return false;
        }
        //判断是否边重复
        EdgeNode* ptmp = m_VertexArray[idx1].point;
        while(ptmp != nullptr){
            if(ptmp->curridx == idx2){
                cout<<"该边已经存在，请勿重复插入！"<<endl;
                return false;
            }
            ptmp = ptmp->next;
        }
        ptmp = new EdgeNode;
        ptmp->curridx = idx2;
        ptmp->next = m_VertexArray[idx1].point;
        m_VertexArray[idx1].point = ptmp;

//        ptmp = new EdgeNode;
//        ptmp->curridx = idx1;
//        ptmp->next = m_VertexArray[idx2].point;
//        m_VertexArray[idx2].point = ptmp;
        m_numEdges++;
        return true;
    }
    //删除边
    bool DeleteEdge(const T& tmpv1,const T& tmpv2){
        int idx1 = GetVertexIdx(tmpv1);
        int idx2 = GetVertexIdx(tmpv2);
        if (idx1 == -1 || idx2 ==-1){
            cout<<"存在非法顶点，无法删除边！"<<endl;
            return false;
        }
        //在第一个节点中查找边信息
        EdgeNode* prev = nullptr;//指向前驱节点方便做删除边界点的操作
        EdgeNode* ptmp = m_VertexArray[idx1].point;
        while(ptmp != nullptr && ptmp->curridx != idx2 ){
            prev = ptmp;
            ptmp = ptmp->next;
        }
        if(ptmp == nullptr){     //两个节点之间没有边
            cout<<"两节点间不存在连边，无法删除！"<<endl;
            return false;
        }
        //有边，则可以删除
        if(prev == nullptr){
            m_VertexArray[idx1].point= ptmp->next;
        }
        else {
            prev->next = ptmp->next;
        }
        delete ptmp;

        //在第二个节点中查找边
        prev = nullptr;//指向前驱节点方便做删除边界点的操作
        ptmp = m_VertexArray[idx2].point;
        while(ptmp != nullptr && ptmp->curridx != idx1 ){
            prev = ptmp;
            ptmp = ptmp->next;
        }
        if(ptmp == nullptr){     //两个节点之间没有边
            cout<<"两节点间不存在连边，无法删除！"<<endl;
            return false;
        }
        //有边，则可以删除
        if(prev == nullptr){
            m_VertexArray[idx2].point= ptmp->next;
        }
        else {
            prev->next = ptmp->next;
        }
        delete ptmp;
        m_numEdges--;
        return true;
    }
    //删除顶点
    bool DeleteVertex(const T& tmpv){
        int idx = GetVertexIdx(tmpv);
        if (idx == -1)//顶点不存在
        {
            cout<<"顶点不存在，无法删除！"<<endl;
            return false;
        }
        EdgeNode* ptmp = m_VertexArray[idx].point;
        while(ptmp != nullptr){
            int tmpDestIdx = ptmp->curridx;
            EdgeNode* ptmpDestPrev = nullptr;
            EdgeNode* ptmpDest = m_VertexArray[tmpDestIdx].point;
            while( ptmpDest != nullptr && ptmpDest->curridx != idx){
                ptmpDestPrev = ptmpDest;
                ptmpDest = ptmpDest->next;
            }
            if (ptmpDestPrev == nullptr){
                m_VertexArray[tmpDestIdx].point = ptmpDest->next;
            }
            else{
                ptmpDestPrev->next=ptmpDest->next;
            }
            delete ptmpDest;
            m_VertexArray[idx].point = ptmp->next;
            delete(ptmp);
            ptmp = m_VertexArray[idx].point;
            m_numEdges--;//边数量减少
        }
        m_numVertices--;
        if( idx != m_numVertices){
            //要删除的不是最后一个顶点
            m_VertexArray[idx].data = m_VertexArray[m_numVertices].data;
            m_VertexArray[idx].point = m_VertexArray[m_numVertices].point;
            EdgeNode* ptmpnew = m_VertexArray[idx].point;
            while(ptmpnew != nullptr){
                int tmpIdx = ptmpnew->curridx;
                EdgeNode* tmp = m_VertexArray[tmpIdx].point;
                while(tmp != nullptr){
                    if(tmp->curridx == m_numVertices){
                        tmp->curridx = idx;
                        break;     //直接跳出while
                    }
                    tmp = tmp->next;
                }
                ptmpnew = ptmpnew->next;
            }
        }
        m_VertexArray[m_numVertices].point = nullptr;
        return true;
    }
    //获取某个顶点的第一个邻接顶点的下标
    int GetFirstNeighbor(int idx){
        if (idx == -1 || idx >= m_numVertices)
        {
            return -1;  //非法
        }
        EdgeNode* pedge = m_VertexArray[idx].point;
        if(pedge != nullptr){
            return pedge->curridx;
        }
        return -1;
    }
    //获取某个顶点的邻接顶点的下一个邻接顶点的下标
    int GetNextNeighbor(int idx1,int idx2){
        if (idx1 == -1 || idx1 >= m_numVertices||idx2 == -1 || idx2 >= m_numVertices){
            return -1;//非法
        }
        EdgeNode* pedge = m_VertexArray[idx1].point;
        while(pedge != nullptr){
            if(pedge->curridx == idx2 && pedge->next != nullptr){
                return pedge->next->curridx;
            }
            pedge = pedge->next;
        }
        return -1;
    }
    void DispGraph()   //显示图的信息
    {
        for (int i = 0; i<m_numVertices;i++){
            cout<< i <<"  "<<m_VertexArray[i].data<<":-->";//输出顶点下标和顶点数据
            EdgeNode* ptmp = m_VertexArray[i].point;
            while(ptmp != nullptr){
                cout<<ptmp->curridx<<"-->";
                ptmp = ptmp->next;
            }
            cout<<"nullptr"<<endl;
        }
        cout<<"------------------"<<endl;
    }
    //拓扑排序算法
    bool TopologicalSort(){
        int* pIndegree = new int[m_numVertices];//分配空间记录顶点入度
        ::memset(pIndegree,0,sizeof(int)* m_numVertices);
        //统计各个顶点的入度值
        for(int i = 0;i < m_numVertices;i++){
            EdgeNode* pEdgenode  =m_VertexArray[i].point;
            while(pEdgenode != nullptr){
                pIndegree[pEdgenode->curridx]++;
                pEdgenode = pEdgenode->next;
            }
        }
        //将入度为0的顶点先入栈
        stack<int> tempstack;
        for(int i = 0;i < m_numVertices;i++){
            if(pIndegree[i] == 0){
                tempstack.push(i);//入栈
            }
        }
        int iOutputVexcount = 0;
        while (tempstack.empty() == false){
            //出栈
            int topidx = tempstack.top();//获取栈顶元素
            cout<<m_VertexArray[topidx].data<<" ";//输出没有前驱的节点
            iOutputVexcount++;
            tempstack.pop();//出栈
            //要讲topidx对应顶点的各个临界点的入度-1
            EdgeNode* pEdgenode  =m_VertexArray[topidx].point;
            while(pEdgenode != nullptr){
                if(pIndegree[pEdgenode->curridx] > 0){
                    pIndegree[pEdgenode->curridx]--;
                    if(pIndegree[pEdgenode->curridx] == 0){
                        tempstack.push(pEdgenode->curridx);
                    }
                }
                pEdgenode = pEdgenode->next;
               // pIndegree[pEdgenode->curridx]--;
               // pEdgenode = pEdgenode->next;
            }
        }
        cout<<endl;
        delete [] pIndegree;
        if(iOutputVexcount != m_numVertices){
            //拓扑排序失败
            cout<<"拓扑排序失败"<<endl;
            return false;
        }
        return true;
    }
};
int main(){
    GraphLink<char> gm2;
    //向图中插入顶点
    gm2.InsertVertex('A');
    gm2.InsertVertex('B');
    gm2.InsertVertex('C');
    gm2.InsertVertex('D');
    gm2.InsertVertex('E');
    gm2.InsertVertex('F');
    gm2.InsertVertex('G');
    gm2.InsertVertex('H');
    //向图中插入顶点
    gm2.InsertEdge('A','C');
    gm2.InsertEdge('A','D');
    gm2.InsertEdge('B','C');
    gm2.InsertEdge('C','E');
    gm2.InsertEdge('D','F');
    gm2.InsertEdge('E','G');
    gm2.InsertEdge('F','G');
    gm2.InsertEdge('G','H');
    gm2.DispGraph();
    gm2.TopologicalSort();
//    gm2.DeleteEdge('A','D');
//    gm2.DeleteEdge('E','B');
//    gm2.DeleteEdge('E','C');
//    gm2.DispGraph();
//    gm2.DeleteVertex('C');
//    gm2.DispGraph();
    return 0;
}